package heap;

import java.util.*;

//使用数组存储最大堆
public class MaxHeap {
    List<Integer>  data;

    public MaxHeap() {//无参时初始化数组范围为10
        this(10);
    }

    public MaxHeap(int size) {//初始化动态数组
        data = new ArrayList<>(size);
    }

    public MaxHeap (int[] array){
        data = new ArrayList<>(array.length);//初始化
        for (int i:array
             ) {
            data.add(i);//记住这个add是动态数组的add方法他妈的这里还构造方法对象是data不是MaxHeap，只有对象是MaxHeap时才有自己的add方法可以直接加入
            siftUp(data.size() - 1);
        }


//        for (int i = parent(data.size() - 1) ; i >= 0 ; i--){
//            siftDown(i);
//        }
    }

    //判空
    public boolean isEmpty(MaxHeap maxHeap){
        return data.size() == 0;
    }

    //加入元素
    public void add(int val){
        data.add(val);
        siftUp(data.size() - 1);
    }

    //取出返回堆中最大值，并把他删掉
    public int extractMax(){
        if (data.isEmpty()){
            throw new NoSuchElementException("宝子这里面是空的哟");
        }
        int max = data.get(0);
        int lastVal = data.get(data.size() - 1);

        data.set(0 , lastVal);
        data.remove(data.size() - 1);
        siftDown(0);
        return max;

    }

    //下沉操作
    public void siftDown(int index){
        while (leftChild(index) < data.size()){//这个很妙因为不用考虑0边界
            //更妙的是啥，堆是完全二叉树所以他不可能只有右子树没有左子树
            int maxChildIndex = leftChild(index);
            if (maxChildIndex + 1 < data.size() && data.get(maxChildIndex + 1) > data.get(maxChildIndex)){
                maxChildIndex = maxChildIndex + 1;
            }
            if (data.get(index) >= data.get(maxChildIndex)){
                break;
            }else {
                swap(index , maxChildIndex);
                index = maxChildIndex;
            }

            //注意这个下面这个想法
//            if (rightChild(index) < data.size()){
//                maxChild = Math.max(data.get(leftChild(index)) , data.get(rightChild(index)));
//            }else {
//                maxChild = data.get(leftChild(index));
//            }
//            swap(data.get(index) , maxChild);
            //但是下一步会发生什么，这里需要用到子树较大的那个的索引，所以要取一个临时值做记录
        }
    }

    //上浮操作
    public void siftUp(int index){
        while (index > 0 && data.get(index) > data.get(parent(index))){
            swap(index , parent(index));
            index = parent(index);
        }

    }

    //交换两个索引的值
    public void swap(int index1 , int index2){
        int temp = data.get(index1);
        data.set(index1 , data.get(index2));
        data.set(index2 , temp);
    }

    //字符串输出他
    public String toString(){//注意这个方法，注意所有操作都是在data即内部数据进行的
       return data.toString();
    }

    //根据索引找父节点的索引
    public int parent(int index){
        return (index - 1) >> 1;
    }

    //根据索引找左子树索引
    public int leftChild(int index){
        return (index << 1) + 1;
    }

    //根据索引找右子树索引
    public int rightChild(int index){
        return (index << 1) + 2;
    }
}
